#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-09-29 9:32 上午
# @Author  : yangdy
# @File    : 2020-09-29.145.二叉树的后序遍历
# @Software: PyCharmCE
from tools.my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        # 1. dfs
        # ans = []

        # def dfs(rt):
        #     if not rt:
        #         return rt
        #     dfs(rt.left)
        #     dfs(rt.right)
        #     ans.append(rt.val)
        # dfs(root)

        # 2. while
        display(root)
        ans = []
        cur, stack = root, []
        while cur or stack:
            while cur:
                stack.append(cur)
                # 前序
                # ans.append(cur.val)
                cur = cur.left
            cur = stack.pop()
            # 中序
            # ans.append(cur.val)
            # cur = cur.right  # 前序 or 中序
            # 后序
            if not cur.right or ans and ans[-1] == cur.right.val:
                ans.append(cur.val)
                cur = None
            else:
                stack.append(cur)
                cur = cur.right

        print(ans)
        # ans.reverse()

        return ans


questions = [
    ([1, None, 2, 3],),
    ([3, 1, 2],),
    ([1, 2, 3, 4, 5],),
]

work(questions, lambda q: Solution().postorderTraversal(mk_tree(q[0], TreeNode)))



